package demo1;

import java.util.*;

public class Solution {

    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if(nums.length == 0) { return ret;}

        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(nums[right] != target) { return ret;}
        ret[0] = right;

        left = 0;
        right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        ret[1] = right;
        return ret;
    }

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] < target ? left + 1 : left;
    }

    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }

    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(letters[mid] <= target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return letters[right] > target ? letters[right] : letters[0];
    }

    public int maximumCount(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] <= 0){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        int l1 = nums[right] == 0 ? 0 : n - right;

        left = 0; right = n - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] >= 0){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        int l2 = nums[right] == 0 ? 0 : right + 1;
        return Math.max(l1, l2);
    }


    public int maximumCount2(int[] nums) {
        int l1 = lowerBound(nums, 0);
        int l2 = nums.length - lowerBound(nums, 1);
        return Math.max(l1, l2);
    }
    public int lowerBound(int[] nums, int val){
        int l = 0, r = nums.length;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < val){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);

        int[] t = new int[spells.length];
        for(int i = 0; i < spells.length; i++){
            double cur = success * 1.0 / spells[i];
            int l = 0, r = potions.length - 1;
            while(l < r){
                int mid = l + (r - l) / 2;
                if(potions[mid] < cur){
                    l = mid + 1;
                }else{
                    r = mid;
                }
            }
            if(potions[r] * 1L * spells[i] >= success) { t[i] = potions.length - r;}
        }
        return t;
    }

    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);

        int ret = 0;
        for(int x : arr1){
            int low = x - d;
            int high = x + d;
            if(!binarySearch(arr2, low, high)){
                ret++;
            }
        }
        return ret;
    }
    public static boolean binarySearch(int[] t, int low, int high){
        int left = 0, right = t.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(t[mid] >= low && t[mid] <= high){
                return true;
            }else if(t[mid] < low){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
    }

    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        for(int i = 1; i < nums.length; i++){
            nums[i] += nums[i - 1];
        }
        for(int i = 0; i < queries.length; i++){
            queries[i] = upperBound(nums, queries[i]);
        }
        return queries;
    }
    public int upperBound(int[] nums, int x){
        int left = -1, right = nums.length;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > x){
                right = mid;
            }else{
                left = mid;
            }
        }
        return right;
    }

    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] count = new int[12];
        for(String s : words){
            count[f(s)]++;
        }
        for(int i = 9; i >= 1; i--){
            count[i] += count[i + 1];
        }
        int[] ret = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            String s = queries[i];
            ret[i] = count[f(s) + 1];
        }
        return ret;
    }
    public int f(String s){
        int cnt = 0;
        char ch = 'z';

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c < ch){
                ch = c;
                cnt = 1;
            }else if(c == ch){
                cnt++;
            }
        }
        return cnt;
    }

    public int[] numSmallerByFrequency2(String[] queries, String[] words) {
        int n = words.length;
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = f(words[i]);
        }
        Arrays.sort(nums);

        int m = queries.length;
        int[] ans = new int[m];
        for(int i = 0; i < m; i++){
            int x = f(queries[i]);
            int l = 0, r = n;
            while(l < r){
                int mid = l+ (r - l) / 2;
                if(nums[mid] <= x){
                    l = mid + 1;
                }else{
                    r = mid;
                }
            }
            ans[i] = n - l;
        }
        return ans;
    }

    public int f2(String s){
        int[] cnt = new int[26];
        for(int i = 0; i < s.length(); i++){
            cnt[s.charAt(i) - 'a']++;
        }
        for(int x : cnt){
            if(x > 0) { return x;}
        }
        return 0;
    }

    public List<Integer> solveQueries(int[] nums, int[] queries) {
        Map<Integer, List<Integer>> indices = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            indices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        int n = nums.length;
        for(List<Integer> p : indices.values()){
            //前后各加一个哨兵
            int i = p.get(0);
            p.add(0, p.get(p.size() - 1) - n);
            p.add(i + n);
        }

        List<Integer> ans = new ArrayList<>(queries.length);  //预分配空间
        for(int i : queries){
            List<Integer> p = indices.get(nums[i]);
            if(p.size() == 3){
                ans.add(-1);
            }else{
                int j = Collections.binarySearch(p, i);
                ans.add(Math.min(i - p.get(j - 1), p.get(j + 1) - i));
            }
        }
        return ans;
    }
}
